package com.qch.edu.lagou.algorithm.greedy;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Author qch
 * @Date 2021/7/22
 * 部分背包：贪心算法
 *
 * 假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，
 * 一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，
 * 可以带走某件物品的一部分，请问：他应该选择哪些物品
 */
public class BagPart {
    //最大承重
    double max=80;
    public double getMaxValue(Goods[] glist)
    {
        double allPrivice=0;
        List<Goods> sortGlist = Arrays.asList(glist);
        Collections.sort(sortGlist);//价值排序
        //当前总重
        double sum_w=0;
        for (int i = 0; i < sortGlist.size(); i++) {
            sum_w+=sortGlist.get(i).weight;
            if(sum_w<=max)
            {
                allPrivice+=sortGlist.get(i).price;
                System.out.println(sortGlist.get(i).name+"已经全被被装完了"+sortGlist.get(i).weight+"kg");

            }else {
                double aweight=max-(sum_w-sortGlist.get(i).weight);
                allPrivice+=sortGlist.get(i).value*aweight;
                System.out.println(sortGlist.get(i).name+"取"+aweight+"kg");
                return allPrivice;
            }
        }
        return allPrivice;
    }

    public static void main(String[] args) {
        BagPart getMaxValue=new BagPart();
        Goods goods3 = new Goods("C", 30, 120);
        Goods goods1 = new Goods("A", 10, 60);
        Goods goods2 = new Goods("B", 20, 100);

        Goods[] goods={goods1,goods2,goods3};
        double maxValue = getMaxValue.getMaxValue(goods);
        System.out.println(maxValue);
    }

}
